This invention relates to a printer having a processor that executes a program stored in memory in the printer, and to systems and methods of executing stored program instructions.
A conventional laser printer generally includes a print engine, an input interface for receiving data to be printed, and a processor that supplies data to the print engine in response to the received input data. The input data conventionally includes instructions conforming to a page description language (PDL), such as PCL printer control language, marketed by Hewlett Packard, or the Postscript page description language, marketed by Adobe Systems. Due to the variety of instructions available in a PDL, a program written to process PDL instructions (a PDL interpreter) is usually fairly large, for example, on the order of 2 MByte. Storage of such a PDL interpreter program is conventionally provided in the printer in read only memory (ROM).
Generally two types of memory are used in the conventional laser printer. Programs having instructions to be executed by the processor, for example, may be stored in ROM or read/write memory; while variables used by the program (including data received to be printed) is stored in read/write memory. Memory systems are expandable so that the factory or user may add support for xe2x80x9cbuilt-inxe2x80x9d features by adding additional preprogrammed ROM modules. Support for processing large amounts of data to be printed on a single sheet may be expanded by the factory or user by adding random access memory (RAM) modules for the read/write memory functions.
Generally, ROM access time is longer than the access time for RAM. Therefore, program instructions fetched from a ROM (e.g. for a PDL interpreter) will execute slower than program instructions fetched from a RAM. RAM, however, generally costs more than ROM. Although a user may add RAM to a printer, for example, to print complex images and to store a downloaded PDL interpreter (located in RAM for higher execution speed) the PDL interpreter may take up a great deal of RAM, offsetting the ability of the printer to print complex images.
Without methods and systems of the present invention, the ability of a user to expand the capability of a printer will be limited. Users expect printers to print more complex images and interpret more complex PDLs. Cost and system reliability constraints, among other factors, limit the ability to meet these demands by simply adding RAM. Without the ability to expand printer capability in response to system software expansion, conventional printers become obsolete too quickly.
In view of the problems described above and related problems, the need remains particularly in printers, and generally in processors, for systems and methods of efficiently storing and executing programs.
A printer in one embodiment of the present invention includes a memory, a buffer, and a formatter. The memory stores a program in compressed form. The buffer receives input data from a provided computer. The formatter is coupled to the memory and to the buffer and determines an image in response to the input data. The formatter includes a decompressor, a cache, and a processor. The formatter receives at least a portion of the program from the memory and decompresses the portion to provide an instruction. The cache receives and stores the instruction. The processor receives the instruction from the cache and determines the image by executing the instruction. The print engine prints the image as determined by the formatter.
According to a first aspect of such an embodiment, storage of the program in memory requires less address space. Consequently, the printer may be provided at the same cost with more or longer programs, or the amount of memory may be reduced to reduce the cost of manufacturing the printer.
According to a second aspect, execution of the program fetched from the cache is faster than execution of an expanded program fetched from the memory. When the fetch access time for cache is much faster than the fetch access time for memory, a time savings develops that is more than sufficient for decompression, leaving a substantial net execution time savings.
According to another aspect, execution of a program for interpreting input data for forming an image to be printed is faster when program instructions are fetched from cache instead of being fetched from memory. Faster execution time permits a higher printing rate with respect to the same interpretation requirement or permits an alternate more sophisticated interpretation without adversely affecting the printing rate.
An integrated circuit in one embodiment of the present invention includes a processor and a cache. The processor provides an address for fetching an executable instruction. The cache provides the executable instruction in response to the address. The cache includes a memory and a decompressor. The decompressor reads a table and an information block from a provided system memory. The table includes a plurality of rows. Each row corresponds to a respective tag value taken from a series of tag values. Each row also identifies a respective code block value. The information block includes a data item. The decompressor stores in the cache memory a copy of the respective code block value of a selected row of the table. The selected row has a tag value identified by the data item. The code block includes the executable instruction and has more bits than the data item. A net decompression results from the substitution of the code block value for the data item.
According to an aspect, of such an embodiment, storage of the program in the provided memory requires less address space. Consequently, systems using the integrated circuit may be provided at the same cost with more or longer programs, or the amount of system memory may be reduced to reduce the cost of systems manufacturing.
According to a second aspect, execution of the program fetched from the cache is faster than execution of an expanded program fetched from system memory. When the fetch access time for cache is much faster than the fetch access time for system memory, a time savings develops that is more than sufficient for decompression, leaving a substantial net execution time savings.
Another embodiment of the present invention provides a method for storing a series of executable instructions for later execution from a cache. The method includes the steps of determining a pattern size; dividing the series of instructions into a series of code blocks, each code block having a respective code block value and having the pattern size; for each occurrence of a code block value in the series of instructions, incrementing a respective count associated with the respective code block value; determining a series of tag values, forming a table having a row for each tag value, and determining a tag value having no corresponding row; interactively selecting the maximum unselected count and placing in the table for a respective tag value the respective code block value, until all rows have been filled; determining a series of information blocks by interactively reading in series a code block from the series of code blocks and, for each code block value that corresponds to a row of the table, identifying in the information block the tag value of the corresponding row, and otherwise, when no corresponding row exists in the table, identifying in the information block the tag value having no corresponding row followed by the respective code block value; and storing the table and the series of information blocks in a memory for access by a decompressor that writes the cache in response to code block values of the table and to code block values of the information blocks, so that the cache contains executable instructions.
According to a first aspect of such a method, the resulting information blocks occupy less space than the series of instructions. A net compression is achieved with consequent savings in the cost of storing the series of instructions.
According to another aspect, because the number of bits in the pattern size may vary from the number of bits in one instruction, recurring groups of instructions may be recognized for compression, or recurring subsets of bits in several instructions may be recognized for compression.